package linkedlist;

/**
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
 * 每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
 * 这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 * 返回一个由上述 k 部分组成的数组。
 */
public class no725 {
    public static void main(String[] args) {
        ListNode node = creat();
        ListNode[] nodes = splitListToParts(node,3);
    }
    public static ListNode creat(){
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(7);
        ListNode listNode8 = new ListNode(8);
        ListNode listNode9 = new ListNode(9);
        ListNode listNode10 = new ListNode(10);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        listNode6.next = listNode7;
        listNode7.next = listNode8;
        listNode8.next = listNode9;
        listNode9.next = listNode10;
        return listNode1;
    }
    public static ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] nodes = new ListNode[k];
        if(head == null){
            return nodes;
        }
        ListNode cur = head;
        int size = 0;
        while (cur != null){
            size++;
            cur = cur.next;
        }
        cur = head;
        int every;
        int add = size % k ;
        int i = 0;
        while (cur != null){
            every = size / k;
            ListNode prev = cur;
            if (i < k){
                nodes[i] = cur;
            }
            while (every > 0){
                prev = cur;
                cur = cur.next;
                every--;
            }
            if (add > 0){
                prev = cur;
                cur = cur.next;
                add--;
            }
            if (cur != null){
                prev.next = null;
            }
            i++;
        }
        return nodes;
    }
}
